% This file was created with JabRef 2.3.1.
% Encoding: GBK

@ARTICLE{network,
  author = {Gkantsidis, Christos and Mihail, Milena and Saberi, Amin},
  title = {Random walks in peer-to-peer networks: Algorithms and evaluation},
  journal = {Performance Evaluation},
  year = {2006},
  volume = {63},
  pages = {241--263},
  number = {3},
  month = {March},
  abstract = {We quantify the effectiveness of random walks for searching and construction
	of unstructured peer-to-peer (P2P) networks. We have identified two
	cases where the use of random walks for searching achieves better
	results than flooding: (a) when the overlay topology is clustered,
	and (b) when a client re-issues the same query while its horizon
	does not change much. Related to the simulation of random walks is
	also the distributed computation of aggregates, such as averaging.
	For construction, we argue that an expander can be maintained dynamically
	with constant operations per addition. The key technical ingredient
	of our approach is a deep result of stochastic processes indicating
	that samples taken from consecutive steps of a random walk on an
	expander graph can achieve statistical properties similar to independent
	sampling. This property has been previously used in complexity theory
	for construction of pseudorandom number generators. We reveal another
	facet of this theory and translate savings in random bits to savings
	in processing overhead.},
  booktitle = {P2P Computing Systems},
  citeulike-article-id = {3169823},
  doi = {http://dx.doi.org/10.1016/j.peva.2005.01.002},
  keywords = {algorithms, p2p, random-walks},
  owner = {jimmy},
  posted-at = {2008-08-28 15:52:32},
  priority = {3},
  timestamp = {2009.01.16},
  url = {http://dx.doi.org/10.1016/j.peva.2005.01.002}
}

@MISC{fan,
  author = {Fan Chung Graham},
  title = {Random Walks on Directed and Undirected Graphs, lecture notes},
  howpublished = {http://www.math.ucsd.edu/~phorn/math261/},
  year = {2008},
  owner = {jimmy},
  timestamp = {2009.01.16},
  url = {http://www.math.ucsd.edu/~phorn/math261/}
}

@ARTICLE{expander,
  author = {Hoory, Shlomo and Linial, Nathan and Wigderson, Avi },
  title = {Expander graphs and their applications},
  journal = {Bull. Amer. Math. Soc. (N.S.)},
  year = {2006},
  volume = {43},
  number = {4},
  citeulike-article-id = {1205008},
  keywords = {bibtex-import, expander-graph, graph, random-graph, random-walk},
  owner = {jimmy},
  posted-at = {2007-04-03 22:06:15},
  priority = {2},
  timestamp = {2009.01.16}
}

@INPROCEEDINGS{quantum,
  author = {Frederic Magniez and Ashwin Nayak and Jeremie Roland and Miklos Santha},
  title = {Search via quantum walk},
  booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on
	Theory of computing},
  year = {2007},
  pages = {575--584},
  address = {New York, NY, USA},
  publisher = {ACM},
  doi = {http://doi.acm.org/10.1145/1250790.1250874},
  isbn = {978-1-59593-631-8},
  location = {San Diego, California, USA},
  owner = {jimmy},
  timestamp = {2009.01.16}
}

@ARTICLE{mixing_time,
  author = {R. Montenegro and P. Tetali},
  title = {Mathematical aspects of mixing times in Markov chains},
  journal = {Found. Trends Theor. Comput. Sci.},
  year = {2006},
  volume = {1},
  pages = {237--354},
  number = {3},
  address = {Hanover, MA, USA},
  doi = {http://dx.doi.org/10.1561/0400000003},
  issn = {1551-305X},
  owner = {jimmy},
  publisher = {Now Publishers Inc.},
  timestamp = {2009.01.16}
}

@BOOK{randomized_book,
  title = {Randomized Algorithms},
  publisher = {Cambridge University Press},
  year = {1995},
  author = {Motwani, R. and Raghavan, P. },
  address = {New York, NY, USA},
  citeulike-article-id = {3503974},
  keywords = {file-import-08-11-11},
  owner = {jimmy},
  posted-at = {2008-11-11 15:43:05},
  priority = {0},
  timestamp = {2009.01.16}
}

@ARTICLE{stcon,
  author = {Omer Reingold},
  title = {Undirected connectivity in log-space},
  journal = {J. ACM},
  year = {2008},
  volume = {55},
  pages = {1--24},
  number = {4},
  address = {New York, NY, USA},
  doi = {http://doi.acm.org/10.1145/1391289.1391291},
  issn = {0004-5411},
  owner = {jimmy},
  publisher = {ACM},
  timestamp = {2009.01.16}
}

@INPROCEEDINGS{spectral,
  author = {Daniel A. Spielman},
  title = {Spectral Graph Theory and its Applications},
  booktitle = {FOCS '07: Proceedings of the 48th Annual IEEE Symposium on Foundations
	of Computer Science},
  year = {2007},
  pages = {29--38},
  address = {Washington, DC, USA},
  publisher = {IEEE Computer Society},
  note = {Yale University-Daniel A. Spielman},
  doi = {http://dx.doi.org/10.1109/FOCS.2007.66},
  isbn = {0-7695-3010-9},
  owner = {jimmy},
  timestamp = {2009.01.16}
}

